package linkedlist;
//表示链表的节点
class Node {
    // 节点保存值
    public String value;
    // 指向下一个节点
    public Node next;

    public Node(String value) {
        this.value = value;
        this.next = null;
    }
}


public class MyLinkedList {
         //把链表的头节点表示出来，此时整个链表就能获取了
    //此时不包含傀儡节点，head==null的时候表示空链表
    private Node head=null;
    //不像顺序表使用size表示区间的长度，链表使用length表示链表的长度
    //但也可以使用size表示个数。

    //插入元素
    //1：尾插(先找到尾巴，再插入)
    public void addlast(String value){
        //如果链表为空
        if(head==null){
            //新建一个节点
            Node newNode=new Node(value);
            //把新节点放到头部
            head=newNode;
            return;
        }
        //先找道尾巴，把新的节点加道尾巴后面
        //先创建一个头节点
        Node tail=head;
        for(;tail.next!=null;tail=tail.next){
            if(tail.next==null){
                break;
            }
        }//找到尾巴
        //新建一个节点

        Node newNode=new Node(value);
        tail.next=newNode;
        newNode.next=null;

    }
    //2：头插(
    public void addfirst(String value) {
            //新建一个节点
            Node newNode = new Node(value);
            //把新节点放到头部
            //1：就要将newNode的next指向head指向的节点
            newNode.next = head;
            //2：然后我们的head在指向（新节点）newNode
            head = newNode;
    }

    //3：指定位置插入
    //在链表中没有下标的概念
    //链表需要遍历，找位置。
    //但是java标准库，LinkedList同样引入下标这个概念，使用List统一作为ArrayList和LinkedList的接口
    public void add(int index,String value) {
        //先判断index是否合法
        if (index < 0 || index > size()) {//index==size等于尾插，没必要判断
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }
        //针对头插出现的情况
        if(index==0){
            addfirst(value);
            return;
        }
        //根据当前value值，创建新的节点
        Node cur = new Node(value);
        //找到index位置的前一个节点
        //由于当前链表是单向链表，每个节点稚只能找到next节点
        //需要修改前一个节点next的值，让它指向当前节点
        //插入新节点，需要找到index-1位置的节点
        Node prev = head;
        for(int i=0;i<index-1;i++){
            prev=prev.next;
        }
        cur.next=prev.next;
        prev.next=cur;
    }
    //虽然没有size()方法，我们可以自己写一个，遍历链表，计算长度
    public int size() {
        int size = 0;
        for(Node cur =head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
    }
    //判断某个元素是否存在链表中
    public Boolean contains(String value){
        //遍历链表，判断是否有value
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.value.equals(value)){
                return true;
            }
        }
        return false;
    }

    //indexOf方法，查找某个元素的位置
    public int indexOf(String value){
        int index=0;
        for(Node cur=head;cur!=null;cur=cur.next){
            //每次判断值是否相等，找到就返回index，没有找到就继续遍历index++
            if(cur.value.equals(value)){
                return index;
            }
            index++;
        }
        return -1;
    }

    //remove方法，删除列表中的元素,根据下标删除
    //根据下标删除，需要先找到index位置的前一个节点，然后将前一个节点的next指向index+1位置的节点
    public void remove(int index){
        if(index<0||index >= size()){
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }
        //特殊处理index为0的情况
        if(index==0){
            head=head.next;
            return;
        }
        //找到被删除元素前一个节点位置
        Node prev=head;
        for(int i=0;i<index-1;i++) {
            prev = prev.next;
        }
        //循环结束，prev就指向待删除元素的前一个节点
        Node delNode=prev.next;
        //将prev的next指向待删除元素的下一个节点
        prev.next=delNode.next;
        delNode.next=null;
    }
    //remove方法，删除列表中的元素,根据值删除
    //根据值删除，需要先找到值所在的节点，然后将前一个节点的next指向index+1位置的节点
    public void remove(String value){
        //判读链表是否为空
        if(head==null){
            return;
        }
        //要删除的元素是头节点
        if(head.value.equals(value)){
            //直接将头节点指向头节点的下一个节点
            head=head.next;
            return;
        }
        //先找到值所在的节点
        Node prev=head;
        for(;prev!=null;prev=prev.next){
            if(prev.next!=null&&prev.next.value.equals(value)){
                break;
            }
        }
        //循环结束，prev就指向待删除元素的前一个节点
        if(prev==null){
            return ;
        }
        //将prev的next指向待删除元素的下一个节点
        Node delNode=prev.next;
        //将prev的next指向待删除元素的下一个节点
        prev.next=delNode.next;
        delNode.next=null;
    }
    public void clear() {
        //清空链表
        //直接没有指向头节点的指针，就表示链表为空
        head=null;
    }


    @Override
    public String toString() {
         //通过这个方法，遍历链表，构成一个字符串，方便打印
        //遍历的时候，需要从头节点开始，进行一个一个元素打印
        StringBuilder stringbuilder=new StringBuilder();
        stringbuilder.append("[");
        for(Node cur=head;cur!=null;cur=cur.next){
            //NOde cur=head : 指向头节点(开始遍历，取头节点)
            //cur!=null : 循环条件，当cat不为null的时候，才进行循环
            //cur.next : 指向下一个节点（把下一个节点取出来）
            stringbuilder.append(cur.value);
            //当前我们不希望最后一个元素后面带上逗号，所以这里判断一下
            if(cur.next!=null) {
                stringbuilder.append(",");
            }
        }
        stringbuilder.append("]");
        return stringbuilder.toString();
    }

    private static void test1(){
        MyLinkedList list=new MyLinkedList();
        list.addfirst("a");
        list.addfirst("b");
        list.addfirst("c");
        list.addfirst("d");
        list.addfirst("e");
        //还需要遍历链表才能打印出元素
        System.out.println(list.toString());
        }
        public static void  test2(){
            MyLinkedList list=new MyLinkedList();
            list.addlast("a");
            list.addlast("b");
            list.addlast("c");
            list.addlast("d");
            list.addlast("e");
            //还需要遍历链表才能打印出元素
            System.out.println(list.toString());
        }
        public static void  test3(){
            MyLinkedList list=new MyLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.add(3,"d");
            list.add(4,"e");
            list.add(2,"lllllll");
            System.out.println(list.toString());
        }
        public static void  test4(){
            MyLinkedList list=new MyLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.add(3,"d");
            list.add(4,"e");
            System.out.println(list.contains("a"));//true
            System.out.println(list.contains("f"));//false
        }
        public static void  test5(){
            MyLinkedList list=new MyLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.add(3,"d");
            list.add(4,"e");
            System.out.println(list.indexOf("a"));
            System.out.println(list.indexOf("f"));
        }
        public static void  test6(){
            MyLinkedList list=new MyLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.add(3,"d");
            list.add(4,"e");
            list.remove(2);
            System.out.println(list.toString());
        }
        public static void  test7(){

        MyLinkedList list=new MyLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.add(4,"e");
        list.remove("c");
        System.out.println(list.toString());
        }
        public static void  test8(){
            MyLinkedList list=new MyLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.add(3,"d");
            list.add(4,"e");
            list.clear();
            System.out.println(list.toString());
        }
    public static void main(String[] args) {
        test1();//头插
        test2();//尾插
        test3();//测试中间元素
        test4();//测试元素是否存在
        test5();//测试元素的位置
        test6();//测试删除元素
        test7();//测试根据值删除元素
        test8();//测试情况链表为空
    }

}

